package one;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
 * <p>
 * The same repeated number may be chosen from C unlimited number of times.
 * <p>
 * Note:
 * <p>
 * All numbers (including target) will be positive integers.
 * Elements in a combination (a1, a2, ... , ak) must be in non-descending order. (ie, a1 ? a2 ? .. ? ak).
 * The solution set must not contain duplicate combinations.
 * For example, given candidate set 2,3,6,7 and target 7,
 * A solution set is:
 * [7]
 * [2, 2, 3]
 * <p>
 * ===================================
 * <p>
 * 1. sort the array
 * 2. be careful of the index of current recurrence.
 * 3. avoid same key in same recurrence
 */
public class Day10_Combination_Sum {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (candidates.length == 0) {
            return res;
        }
        Arrays.sort(candidates);
        ArrayList<Integer> adds = new ArrayList<Integer>();
        dfs(candidates, 0, target, adds, res);
        return res;
    }

    private void dfs(int[] nums, int index, int target, ArrayList<Integer> adds, ArrayList<ArrayList<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<Integer>(adds));
            return;
        }
        HashSet<Integer> chescks = new HashSet<Integer>();
        for (int i = index; i < nums.length; i++) {
            if (target >= nums.length && !chescks.contains(nums[i])) {
                adds.add(nums[i]);
                dfs(nums, i, target - nums[i], adds, res);
                chescks.add(nums[i]);
                adds.remove(adds.size() - 1);
            }
        }
    }


}
